package com.LC.快排;

/**
 * 随机找出一个数，可以随机取，也可以取固定位置，一般是取第一个或最后一个称为基准，然后就是比基准小的在左边，
 * 比基准大的放到右边，如何放做，就是和基准进行交换，这样交换完左边都是比基准小的，右边都是比较基准大的，
 * 这样就将一个数组分成了两个子数组，然后再按照同样的方法把子数组再分成更小的子数组，直到不能分解为止。
 */
public class _04_通解_未理解 {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        quickSort(arr, 0, arr.length - 1);  // 快排
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) { // 判断是否需要继续进行
            int i = left, j = right;    // 定义左右指针
            int temp = arr[left];    // 定义一个变量存储第一个元素
            while (i < j) {   // 当左指针小于右指针时
                while (i < j && arr[j] >= temp) {   // 当右指针指向的元素大于等于temp时
                    j--;    // 右指针向左移动
                }
                if (i < j) {    // 当右指针指向的元素小于temp时 执行  将右指针指向的元素赋值给左指针
                    arr[i] = arr[j];    // 将右指针指向的元素赋值给左指针
                    i++;    // 左指针向右移动
                }
                while (i < j && arr[i] <= temp) {   // 当左指针指向的元素小于等于temp时
                    i++;    // 左指针向右移动
                }
                if(arr[i] > temp){
                    arr[j] = arr[i];
                    j--;
                }
            }
            arr[i] = temp;  // 将temp赋值给左指针指向的元素
            quickSort(arr, left, i - 1);    // 对左半部分数组进行快排
            quickSort(arr, i + 1, right);   // 对右半部分数组进行快排
        }
    }
}
